package com.grakol.algorithm.samples;

/**
 * Given array of integers, finds 'max sub-array' - contiguous sub-array with 
 * max sum of elements. It calculates and compares sums of all contiguous 
 * sub-arrays of a given array. 
 * @author LK
 *
 */
public class MaxSubArray {
	// structure for storing result
	public static class Result {
		public int left;
		public int length;
		public int value;
		public Result( int length ) {
			this.left = 0;
			this.length = length;
			this.value = Integer.MIN_VALUE;
		}
	}
	/**
	 * Returns Result object representing 'max sub-array' for a given integer 
	 * array.
	 * @param array the given input integer array.
	 * @return Result object representing 'max sub-array' for the given 
	 * input integer array.
	 */
	public Result findMaxSubArray( int[] array ) {
		Result result = findMaxSubArray( array, array.length );
		for( int length = array.length - 1; length > 0; length-- ) {
			Result tmp = findMaxSubArray( array, length );
			if( tmp.value > result.value ) {
				result.left = tmp.left;
				result.length = length;
				result.value = tmp.value;
			}
		}
		return result;
	}
	/**
	 * Returns Result object representing 'max sub-array' of a given length 
	 * for a given integer array.
	 * @param array the given input integer array.
	 * @param length the given sub-array length.
	 * @return Result object representing 'max sub-array' of the given length 
	 * for the given integer array.
	 */
	private Result findMaxSubArray( int[] array, int length ) {
		Result result = new Result( length );
		for( int left = 0; left <= array.length - length; left++ ) {
			// calculate sum of sub-array
			int value = 0;
			for( int i = 0; i < length; i++ )
				value += array[left + i];
			if( value > result.value ) {
				result.left = left;
				result.value = value;
			}
		}
		return result;
	}
}
